package leetcode.onehundred;

//5. 最长回文子串

import java.util.*;

public class LongestPalindrome {
    public static void main(String[] args) {
//        System.out.println(longestPalindromeP2("babad"));
        System.out.println(longestPalindrome409("abccccdd"));
    }

    //暴力----超时
    public String longestPalindrome(String s) {
        int max = 0;
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    res = s.substring(i, j);
                    max = Math.max(max, res.length());
                }
            }
        }
        return res;
    }

    private boolean isPalindromic(String test) {
        int n = test.length();
        for (int i = 0; i < n / 2; i++) {
            if (test.charAt(i) != test.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }


    //dp
    public String longestPalindrome2(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
        char[] charArray = s.toCharArray();

        // 枚举所有长度大于 1 的子串 charArray[i..j]
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 验证子串 s[left..right] 是否为回文串
     */
    private boolean validPalindromic(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    //dp
    public String longestPalindrome3(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);

    }

    // 二战蓝桥，暴力就暴力吧
    public static String longestPalindromeP(String s) {
        String res = "";
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isOK(s.substring(i, j)) && max < s.substring(i, j).length()) {
                    res = s.substring(i, j);
                    max = Math.max(res.length(), max);
                }
            }
        }
        return res;
    }

    // 暴力优化
    public static String longestPalindromeP2(String s) {
        int maxLength = 1;
        int begin = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
               if (j-i+1>maxLength && isOK(s.substring(i,j+1))){
                   maxLength = j-i+1;
                   begin = i;
               }
            }
        }
        return s.substring(begin,begin+maxLength);
    }

    private static boolean isOK(String substring) {
        int p = 0;
        int q = substring.length() - 1;
        while (p < q) {
            if (substring.charAt(p) != substring.charAt(q)) {
                return false;
            }
            p++;
            q--;
        }
        return true;
    }

    // 409. 最长回文串
    public static int longestPalindrome409(String s) {
        int[] arr = new int[128];
        for(char c : s.toCharArray()) {
            arr[c]++;
        }
        int count = 0;
        for (int i : arr) {
            // 只能有一个个数为奇数的字符，所以记录有多少个奇数的，然后把他减去再加上一个允许的即可
            count += (i % 2);
        }
        return count == 0 ? s.length() : (s.length() - count + 1);
    }
}